package threshold;

/**
 * @Author wujiaming
 * @Description TODO
 * @Date 2023-03-12 21:25
 * @Version 1.0
 * 股票买卖问题，对于给定的一个数组下标i可以表示从哪一天买入卖出的股票，计算所得的价格最高
 */
public class MaxProfit {

    /**
     * 暴力求解法，遍历一遍数组，对于遍历的当前数组i的元素prices[i]，再往后遍历数组i之后的元素j，对于当前元素prices[j];
     * 找prices[j]-prices[i]的最大值
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int max = 0,buy,sell;
        for (int i = 0; i <prices.length-1 ; i++) {
            buy = prices[i];
            for (int j = i+1; j <prices.length ; j++) {
                if( (prices[j]-buy) > max){
                    max = prices[j]-buy;
                }
            }
        }


        return max;
    }

    /**
     * 一次遍历数组，找到当前的最低点买入股票，在找当天的对高点售出股票
     * 也是动态规划的思想（当前买入的股指是最小利润时记录下来，当前的利润时最大利润的时记录下来）当遍历一遍数组时就能找到最优解
     * @param prices
     * @return
     */
    public int maxProfit1(int[] prices) {
        int min = Integer.MAX_VALUE;
        int max = 0;
        for (int i = 0; i <prices.length ; i++) {
            if(prices[i]<min){
                min = prices[i];
            }else if(prices[i]-min >max){
                max = prices[i] - min;
            }
        }
        return max;
    }




    public static void main(String[] args) {
        int[] nums = {7,1,5,3,6,4};
        MaxProfit test = new MaxProfit();
        System.out.println(test.maxProfit(nums));
        System.out.println(test.maxProfit1(nums));
    }
}
